package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/16/20 10:23 AM
 */
public class _99_恢复二叉搜索树_01 {



    public void recoverTree(TreeNode root) {

        TreeNode node = root;

        TreeNode beforeNode = null, oneNode = null,twoNode = null;

        while (node != null) {

            if (node.left != null) {

                TreeNode preNode = node.left;
                while (preNode.right != null && preNode.right != node) {

                    preNode = preNode.right;
                }

                if (preNode.right == null) {

                    preNode.right = node;
                    node = node.left;
                }else {

                    preNode.right = null;

                    if (beforeNode != null && beforeNode.val > node.val) {

                        twoNode = node;

                        if (oneNode == null) {

                            oneNode = beforeNode;
                        }
                    }

                    beforeNode = node;

                    node = node.right;
                }

            }else {

                if (beforeNode != null && beforeNode.val > node.val) {

                    twoNode = node;

                    if (oneNode == null) {

                        oneNode = beforeNode;
                    }
                }

                beforeNode = node;
                node = node.right;
            }
        }

        if (oneNode != null && twoNode != null) {

            int tmp = oneNode.val;
            oneNode.val = twoNode.val;
            twoNode.val = tmp;
        }

    }


}
